package P4;

public class P4_findMedianSortedArrays {

    public static void main(String[] args) throws Exception {

        int[] a = new int[]{2,3,4,5,6};
        int[] b = new int[]{1};
        System.out.println(new P4_findMedianSortedArrays().findMedianSortedArrays(a, b));
    }


    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int length1 = nums1.length;
        int length2 = nums2.length;

        if (nums1.length > nums2.length) {
            int[] tmep = nums1;
            nums1 = nums2;
            nums2 = tmep;
        }

        int lengthNum = length1 + length2;

        //特殊情况1：数组为空
        if (nums1.length == 0 || nums2.length == 0) {
            return special1(nums1, nums2);
        }

        //正常：两个数组均有值，且不是【一个数组完全在另一个数组后或者前】的场景
        //右侧数的数量
        int rightNum = (length1 + length2) / 2;

        //代表下标
        int head = 0;
        int tail = nums1.length - 1;

        while (head <= tail) {
            //mid是nums1数组的元素下标
            int mid = (head + tail) / 2;
            //计算另一个数组的个数
            int otherMid = rightNum - (mid + 1);

            //数组1的前半部分下标
            int nums1FirstHalfTailIndex = mid;
            //另一个数组的前一半的尾部下标，可能是负数
            int nums2FirstHalfTailIndex = otherMid - 1;

            //计算分割线两边的数值，4个边界
            //nums1前半部分最后的数字
            int nums1FirstHalfMax = nums1[nums1FirstHalfTailIndex];
            //nums1后半部分最前的数字
            int nums1SecondHalfMin = ((nums1FirstHalfTailIndex + 1) == nums1.length ? Integer.MAX_VALUE : nums1[nums1FirstHalfTailIndex + 1]);

            //nums2前半部分最后的数字
            int nums2FirstHalfMax = (nums2FirstHalfTailIndex == -1 ? Integer.MIN_VALUE : nums2[nums2FirstHalfTailIndex]);
            //nums2后半部分最前的数字
            int nums2SecondHalfMin = (nums2FirstHalfTailIndex + 1 == nums2.length ? Integer.MAX_VALUE : nums2[nums2FirstHalfTailIndex + 1]);

            //如果nums1的前部分尾<nums2后部分头 且 nums2的前部分尾<nums1后部分头，代表找到了
            if (nums1FirstHalfMax <= nums2SecondHalfMin && nums2FirstHalfMax <= nums1SecondHalfMin) {
                return getResult(lengthNum, nums1FirstHalfMax, nums1SecondHalfMin, nums2FirstHalfMax, nums2SecondHalfMin);
            }

            //下面是不符合要求的
            if (nums1FirstHalfMax > nums2SecondHalfMin) {
                tail = mid - 1;
            } else {
                //nums2FirstHalfMax > nums1SecondHalfMin
                head = mid + 1;
            }
        }

        //nums1
        if (tail == -1) {
            head = tail;
        }
        //数组1的前半部分下标
        int nums1FirstHalfTailIndex = head;
        //另一个数组的前一半的尾部下标，可能是负数
        int nums2FirstHalfTailIndex = rightNum - (head + 1) - 1;
        //计算分割线两边的数值，4个边界
        //nums1前半部分最后的数字
        int nums1FirstHalfMax = (nums1FirstHalfTailIndex == -1 ? Integer.MIN_VALUE :  nums1[nums1FirstHalfTailIndex]);
        //nums1后半部分最前的数字
        int nums1SecondHalfMin = ((nums1FirstHalfTailIndex + 1) == nums1.length ? Integer.MAX_VALUE : nums1[nums1FirstHalfTailIndex + 1]);

        //nums2前半部分最后的数字
        int nums2FirstHalfMax = (nums2FirstHalfTailIndex == -1 ? Integer.MIN_VALUE : nums2[nums2FirstHalfTailIndex]);
        //nums2后半部分最前的数字
        int nums2SecondHalfMin = (nums2FirstHalfTailIndex + 1 == nums2.length ? Integer.MAX_VALUE : nums2[nums2FirstHalfTailIndex + 1]);

        return getResult(lengthNum, nums1FirstHalfMax, nums1SecondHalfMin, nums2FirstHalfMax, nums2SecondHalfMin);
    }

    /**
     * @param lengthNum
     * @param nums1FirstHalfMax
     * @param nums1SecondHalfMin
     * @param nums2FirstHalfMax
     * @param nums2SecondHalfMin
     * @return
     */
    private double getResult(int lengthNum, int nums1FirstHalfMax, int nums1SecondHalfMin, int nums2FirstHalfMax, int nums2SecondHalfMin) {
        if (lengthNum % 2 == 0) {
            //偶数
            return (double) (Math.max(nums1FirstHalfMax, nums2FirstHalfMax) + Math.min(nums1SecondHalfMin, nums2SecondHalfMin)) * 1.0 / 2;
        } else {
            //奇数
            return (double) (Math.min(nums1SecondHalfMin, nums2SecondHalfMin));
        }
    }


    /**
     * 特殊情况1：数组为空
     *
     * @param nums1
     * @param nums2
     * @return
     */
    private double special1(int[] nums1, int[] nums2) {
        if (nums1.length == 0 && nums2.length == 0) {
            return (double) 0;
        }

        if (nums1.length == 0) {
            return getSingleMid(nums2);
        }

        if (nums2.length == 0) {
            return getSingleMid(nums1);
        }

        //正常不会到这里
        return 0;
    }

    private double getSingleMid(int[] nums) {
        int length = nums.length;
        if (length % 2 == 0) {
            //偶数
            return (double) ((nums[length / 2] + nums[length / 2 - 1]) * 1.0 / 2);
        } else {
            //奇数
            return (double) (nums[length / 2]);
        }
    }
}
